package Sorting;

import java.util.Arrays; // Only used for test
import java.util.Comparator;

public class MergeSort {

    public static <T extends Comparable<T>> void sort(T[] arr) {
        sort(arr, Comparator.naturalOrder());
    }

    public static <T> void sort(T[] arr, Comparator<T> comparator) {
        sortRange(arr, 0, arr.length, comparator);
    }

    private static <T> void sortRange(T[] arr, int from, int to, Comparator<T> comparator) {
        if (to - from > 1) {
            int middle = (from + to) / 2;
            sortRange(arr, from, middle, comparator);
            sortRange(arr, middle, to, comparator);
            mergeRange(arr, from, middle, to, comparator);
        }
    }

    private static <T> void mergeRange(T[] arr, int from, int middle, int to, Comparator<T> comparator) {
        int leftSize = middle - from;
        int rightSize = to - middle;

        Object[] left = new Object[leftSize];
        Object[] right = new Object[rightSize];

        for (int i = 0; i < leftSize; i++) {
            left[i] = arr[i + from];
        }

        for (int i = 0; i < rightSize; i++) {
            right[i] = arr[i + middle];
        }

        int leftTaken = 0;
        int rightTaken = 0;

        for (int k = from; k < to; k++) {
            // All in the left array is taken - append the right
            if (leftTaken == leftSize) {
                for (int i = 0; i < rightSize - rightTaken; i++) {
                    arr[k + i] = (T) right[rightTaken + i];
                }
                return;
            }

            // All in the right array is taken - append the left
            if (rightTaken == rightSize) {
                for (int i = 0; i < leftSize - leftTaken; i++) {
                    arr[k + i] = (T) left[leftTaken + i];
                }
                return;
            }

            // Find the smallest element, and add it
            if (comparator.compare((T) left[leftTaken], (T) right[rightTaken]) <= 0) {
                arr[k] = (T) left[leftTaken];
                leftTaken++;
            } else {
                arr[k] = (T) right[rightTaken];
                rightTaken++;
            }
        }
    }


    public static void main(String[] args) {
        // Testing sort giving class Integer that has a compareTo method
        Integer[] test = new Integer[]{5, 2, 24, 8, 1, 36, 42, 80, 20, 56};
        sort(test);
        System.out.println(Arrays.deepToString(test));

        System.out.println();

        // Testing sort giving class Dog that does not have a compareTo method
        // Also testing if the sort is stable
        Dog[] test2 = new Dog[]{
                new Dog("Carl", 3),
                new Dog("Wuffer", 4),
                new Dog("Carl", 4),
                new Dog("Irena", 2)
        };
        sort(test2, (dog1, dog2) -> (dog1.name.compareTo(dog2.name)));
        System.out.println(Arrays.deepToString(test2));
    }

    private static class Dog {
        String name;
        int age;

        Dog(String name, int age) {
            this.name = name;
            this.age = age;
        }

        public String toString() {
            return name + " " + age;
        }
    }

}
